package 数据结构.树;

import java.util.Stack;

/**
 * @author Zhu
 * @Description
 * @create 2023-02-25
 */
public class JZ82二叉树中和为某一值的路径1 {
    //递归
    public boolean hasPathSum (TreeNode root, int sum) {
        // write code here
        if(root == null)
            return false;
        if(root.left==null && root.right==null && sum - root.val == 0)
            return true;
        return hasPathSum(root.left,sum-root.val) || hasPathSum(root.right,sum-root.val);
    }

    //非递归
    /**
     * dfs
     * step 1：首先检查空节点，空树没有路径。
     * step 2：使用两个栈同步遍历，一个栈记录节点，辅助深度优先搜索，另一个栈跟随记录到该节点为止的路径和。根节点及根节点值先进栈。
     * step 3：遍历的时候每次弹出两个栈中的内容，判断是否是叶子节点且路径和是否等于目标值。
     * step 4：没有到叶子节点就将左右子节点（如果有）加入栈中，并跟随加入路径和。
     * step 5：如果遍历结束也没有找到路径和，则该二叉树中没有。
     */

    public boolean hasPathSum2 (TreeNode root, int sum) {
        if(root==null)
            return false;

        Stack<TreeNode> s1 = new Stack<>();
        Stack<Integer> s2 = new Stack<>();

        s1.push(root);
        s2.push(root.val);
        while(!s1.isEmpty()){
            TreeNode node = s1.pop();
            int cur_sum = s2.pop();
            if(node.left == null && node.right == null && cur_sum == sum)
                return true;

            if(node.left!=null){
                s1.push(node.left);
                s2.push(cur_sum+node.left.val);
            }
            if(node.right!=null){
                s1.push(node.right);
                s2.push(cur_sum + node.right.val);
            }
        }
        return false;
    }
}
